#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class HeapSort {
public:
  /**
   * @brief 堆排序算法（从小往大排）
   *
   * @param a 待调整数组
   * @param len  待调整数组的长度, 这个长度当 a 确定之后随之固定
   */
  static void heapSort(int a[], int len) {
    // 建堆初始化，这里采用下沉操作（下沉比上浮的效率更高）
    for (int i = len / 2; i >= 1; --i) {
      // heapAjust 会将堆调整为大根堆，其中 a[1] 就是数组中最大的元素
      heapAdjust(a, i, len);
    }

    // 每次将最后的叶子结点与堆顶元素进行，然后不断调整，将大的元素放在队列最后，再缩小范围
    for (int i = len; i > 1; --i) {
      swap(a[1], a[i]);
      // 很明显，每次除了 a[i] 之外，其他元素均满足堆的性质，所以起始索引从 1
      // 开始
      heapAdjust(a, 1, i - 1);
    }
  }

  /**
   * @brief 堆排序节点调整算法
   *
   * @param a 待调整数组
   * @param start 待调整序列的起始索引
   * @param end 待调整序列的结束索引
   */
  static void heapAdjust(int a[], int start, int end) {
    for (int i = start * 2; i <= end; i *= 2) {
      // 1. 首先找到当前调整节点的左右孩子中最大的一个
      if (i < end && a[i] < a[i + 1])
        ++i;
      // 2. 如果左右孩子节点中最大的一个比 a[start] 还小 ，直接跳出
      if (a[i / 2] > a[i])
        break;
      // 3. 交换父节点和孩子节点
      swap(a[i / 2], a[i]);
    }
  }
};

int main() {
  int a[12] = {0, 99, 11, -100, 23, 12, 77, 0, -102, 102, 101, 77};
  HeapSort::heapSort(a, 11);
  for (int i = 1; i <= 11; ++i)
    cout << a[i] << " ";
  return 0;
}